﻿namespace ZuoAlgorithms.Class025;

// 堆结构和堆排序
// 测试链接 : https://www.luogu.com.cn/problem/P1177
public class Code01_HeapSort
{
    public static int MAXN = 100001;
    public static int[] arr = new int [MAXN];
    public static int n;

    // i位置的数，向上调整大根堆
    public static void HeapInsert(int i)
    {
        while (arr[i] > arr[(i - 1) / 2])
        {
            Swap(i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    // i位置的数，向下调整大根堆
    // 当前堆的大小为size
    public static void heapify(int i, int size)
    {
        int l = i * 2 + 1;
        while (i < size)
        {
            int best = l + 1 < size && arr[l + 1] > arr[l] ? l + 1 : l;
            best = arr[best] > arr[i] ? best : i;
            if (best == i)
            {
                break;
            }

            Swap(best, i);
            i = best;
            l = i * 2 + 1;
        }
    }

    public static void Swap(int i, int j)
    {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // 从顶到底建立大根堆，O(n * logn)
    // 依次弹出堆内最大值并排好序，O(n * logn)
    // 整体时间复杂度O(n * logn)
    public static void HeapSort1()
    {
        for (int i = 0; i < n; i++)
        {
            HeapInsert(i);
        }

        int size = n;
        while (size > 1)
        {
            Swap(0, --size);
            heapify(0, size);
        }
    }

    // 从底到顶建立大根堆，O(n)
    // 依次弹出堆内最大值并排好序，O(n * logn)
    // 整体时间复杂度O(n * logn)
    public static void HeapSort2()
    {
        for (int i = n - 1; i >= 0; i--)
        {
            heapify(i, n);
        }

        int size = n;
        while (size > 1)
        {
            Swap(0, --size);
            heapify(0, size);
        }
    }
}